package com.SuanFa.jiangdongqi.ErChaShu;

public class BalancedBST {

    // 从有序数组递归创建平衡二叉树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return createBST(nums, 0, nums.length - 1);
    }

    private TreeNode createBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        // 总是选择中间位置右边的元素作为根节点
        int mid = start + (end - start) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = createBST(nums, start, mid - 1);
        root.right = createBST(nums, mid + 1, end);

        return root;
    }

    // 前序遍历
    public void preOrderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    }

    // 中序遍历
    public void inOrderTraversal(TreeNode root) {
        if (root != null) {
            inOrderTraversal(root.left);
            System.out.print(root.val + " ");
            inOrderTraversal(root.right);
        }
    }

    // 后序遍历
    public void postOrderTraversal(TreeNode root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }

    // 查找节点
    public TreeNode search(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val < root.val) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
    }

    public static void main(String[] args) {
        BalancedBST bst = new BalancedBST();
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        // 创建平衡二叉树
        TreeNode root = bst.sortedArrayToBST(sortedArray);

        // 遍历
        System.out.print("前序遍历: ");
        bst.preOrderTraversal(root);
        System.out.println();

        System.out.print("中序遍历: ");
        bst.inOrderTraversal(root);
        System.out.println();

        System.out.print("后序遍历: ");
        bst.postOrderTraversal(root);
        System.out.println();

        // 查找
        int target = 5;
        TreeNode found = bst.search(root, target);
        System.out.println("查找 " + target + ": " + (found != null ? "找到" : "未找到"));

        target = 10;
        found = bst.search(root, target);
        System.out.println("查找 " + target + ": " + (found != null ? "找到" : "未找到"));
    }
}